ABC131 C - Anti-Division

https://atcoder.jp/contests/abc131/tasks/abc131_c

提出

TLE WA

code: python

a, b, c, d = map(int, input().split())

c_divisible = 0

d_divisible = 0

cd_divisible = 0

for i in range(a, b+1):

if (i % c == 0):

c_divisible += 1

if (i % d == 0):

d_divisible += 1

if (i % (c * d) == 0):

cd_divisible += 1

print((b - a + 1) - c_divisible - d_divisible + cd_divisible)

解答

code: python

import math

a, b, c, d = map(int, input().split())

# 0~nまでで、c or dで割り切れない数の個数

def calc_num(n, c, d):

div_c = n // c

div_d = n // d

# n // c,d の最小公倍数

div_cd = n // ((c * d) // math.gcd(c, d))

return n - div_c - div_d + div_cd

# A,Bの個数という問題なので、 0,Bの個数から 0,A-1の個数を引くことで答えを求める。

print(calc_num(b, c, d) - calc_num(a-1, c, d))

テーマ

#gcd

メモ

ABC 131 Anti-Division

提出

code: python

import math

a, b, c, d = map(int, input().split())

# A 以上 B 以下の整数のうち、C でも D でも割り切れない

# (B 以下の整数のうち、C でも D でも割り切れない) - (A-1 以下の整数のうち、C でも D でも割り切れない)

# (B以下の整数 - (Cで割り切れる + Dで割り切れる - CでもDでも割り切れる)) - (A-1以下の整数 - (Cで割り切れる + Dで割り切れる - CでもDでも割り切れる))

def lcm(x, y):

return (x * y) // math.gcd(x, y)

b_c = math.floor(b/c)

b_d = math.floor(b/d)

b_cd = math.floor(b/lcm(c, d))

a_c = math.floor(a/c)

a_d = math.floor(a/d)

a_cd = math.floor(a/lcm(c, d))

print((b - (b_c + b_d - b_cd)) - (a-1 - (a_c + a_d - a_cd)))